Quantum Discrepancy: A Non-Commutative Version of Combinatorial Discrepancy

Abstract

In this paper, we introduce a notion of quantum discrepancy, a non-commutative version of combinatorial discrepancy which is defined for projection systems, i.e. finite sets of orthogonal projections, as non-commutative counterparts of set systems. We show that besides its natural algebraic formulation, quantum discrepancy, when restricted to set systems, has a probabilistic interpretation in terms of determinantal processes. Determinantal processes are a family of point processes with a rich algebraic structure.  A common feature of this family is the local repulsive behavior of points. Alishahi and Zamani (2015) exploit this repelling property to construct low-discrepancy point configurations on the sphere. 

We give an upper bound for quantum discrepancy in terms of $N$, the dimension of the space, and $M$, the size of the projection system, which is tight in a wide range of parameters $N$ and $M$. Then we investigate the relation of these two kinds of discrepancies, i.e. combinatorial and quantum, when restricted to set systems, and bound them in terms of each other.